package FourthWeek;


import java.util.Random;

public class Monday {
    // LRC 159、库存管理III
    public int[] inventoryManagement(int[] stock, int cnt) {
        // Top-k 的问题
        qsort1(stock,0,stock.length - 1,cnt);

        int[] ret = new int[cnt];
        for (int i = 0;i < cnt;i++) {
            ret[i] = stock[i];
        }
        return ret;
    }

    public void qsort1(int[] stock,int l,int r,int cnt) {
        if (l >= r) {
            return;
        }
        // 随机取值
        int key = stock[new Random().nextInt(r - l + 1) + l];
        // 分三份快速排序
        int left = l - 1,right = r + 1,i = l;
        while (i < right) {
            if (stock[i] < key) {
                swap1(stock,++left,i++);
            }else if (stock[i] == key) {
                i++;
            }else {
                swap1(stock,--right,i);
            }
        }

        // 排完序之后呢，我们进行对其三份进行一部分的丢弃根究cnt这个条件
        // 因为我们需要的是小的值，所以我们从左往右开始判断
        // [l,left] [left+1,right-1] [right,r]
        int a = left - l + 1,b = right - left - 1;
        if (a >= cnt) {
            //在最小的那面，继续在最小的那面寻找
            qsort1(stock,l,left,cnt);
        }else if (a + b >= cnt) {
            // 在中间相等的那部分，那么我们就直接返回
            return;
        }else {
            qsort1(stock,right,r,cnt - a - b);
        }
    }

    public void swap1(int[] stock,int i,int j) {
        int tmp = stock[i];
        stock[i] = stock[j];
        stock[j] = tmp;
    }


    // 215、数组中的第k个最大元素
    // Top-k问题有四种提问方式：第k大，第k小，前k大，前k小
    // 还可以使用 堆排 进行解决这个问题
    public int findKthLargest(int[] nums, int k) {
        // 使用快速选择排序解决 Top-k 问题
        return qsort(nums,0,nums.length - 1,k);
    }

    public int qsort(int[] nums,int l,int r,int k) {
        if (l == r) {
            return nums[l];
        }

        // 使用随机的方式进行选择关键字
        int key = nums[new Random().nextInt(r - l + 1) + l];
        // 把数组分成三份
        int left = l - 1,right = r + 1,i = l;
        while (i < right) {
            if (nums[i] < key) {
                swap(nums,++left,i++);
            }else if (nums[i] == key) {
                i++;
            }else {
                swap(nums,--right,i);
            }
        }

        // 分成三份之后，我们根据 k 这个条件对调几份
        int c = r - right + 1,b = right - left - 1;
        // c是最大一部分的长度，b是等于key的区间的长度
        if (c >= k) {
            //第k大的值在 最大的一部分中，把剩余的两个部分丢掉就可以
            return qsort(nums,right,r,k);
        }else if (c + b >= k) {
            // 说明 第k大的值在 中间相等的区间内，直接返回key
            return key;
        }else {
            // 在最小的区间内
            return qsort(nums,l,left,k - b - c);
        }
    }



    // 912、排序数组
    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length - 1);
        return nums;
    }

    public void qsort(int[] nums,int l,int r) {
        if (l >= r) {
            return;
        }

        // 使用随机的方式进行选择基准元素
        // 这个生成的随机数为：[l,r] 之间
        int index = new Random().nextInt(r - l + 1) + l;  // l是偏移量
        int key = nums[index];
        // 使用数组分成三份的思想，实现快排
        int left = l - 1,right = r + 1,i = l;
        while (i < right) {
            if (nums[i] < key) {
                swap(nums,++left,i++);
            }else if (nums[i] == key) {
                i++;
            }else {
                swap(nums,--right,i);
            }
        }

        // [l, left] [left + 1, right - 1] [right, r]
        qsort(nums,l,left);
        qsort(nums,right,r);
    }

    // 75、颜色分类
    private void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    public void sortColors(int[] nums) {
        // 三指针

        // 我们把整个数组分成3份，0-left为0，left+1-right-1为1，right-n-1为2
        int n = nums.length;
        int left = -1,right = n,i = 0;
        // i为遍历数组的指针，left为数字0的最右面的边界，right为2的最左面的边界
        // 0 - left是0
        // left+1 - i-1是1
        // i - right-1为未排序的
        // right - n-1为2

        // nums[i]为：1、0的时候swap(nums[++left],nums[i++])
        //            2、1的时候i++
        //            3、2的时候swap(nums[--right],nums[i])，这里的i不能++，因为交换后的i的位置的值还没有进行处理
        while (i < right) {
            if (nums[i] == 0) {
                swap(nums,++left,i++);
            }else if(nums[i] == 1) {
                i++;
            }else {
                swap(nums,--right,i);
            }
        }
    }


    public void sortColors1(int[] nums) {
        // 单指针
        int n = nums.length;
        int pre = 0;
        for(int i = 0;i < n;i++) {
            if (nums[i] == 0) {
                int tmp = nums[i];
                nums[i] = nums[pre];
                nums[pre] = tmp;
                pre++;
            }
        }

        for (int i = pre;i < n;i++) {
            if (nums[i] == 1) {
                int tmp = nums[i];
                nums[i] = nums[pre];
                nums[pre] = tmp;
                pre++;
            }
        }
    }
}
